package org.example.myleet.rosalind.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationUtil {

    public static boolean hasNextPermutation(int[] prevPerm, int[] curPerm) {
        for (int i = 0; i < prevPerm.length; ++i) {
            if (prevPerm[i] != curPerm[i]) {
                return true;
            }
        }
        return false;
    }

    public static int[] nextPermutation(int[] input) {
        int n = input.length;
        //这里对input做了拷贝，操作过程不影响input
        int[] output = new int[n];
        System.arraycopy(input, 0, output, 0, n);
        if (n < 2) {
            //少于2个字符长度的没有下一个字典序可言
            return output;
        }
        //1、从字符串结尾开始向头部扫描，找到第一个出现降序的字符，满足numbers[i] < numbers[j]，标记j位置
        //解析：能找到这样的位置，说明还存在存在更大的字典序
        int j = n - 1, i = j - 1;
        while (i >= 0) {
            if (output[i] < output[j]) {
                break;
            }
            --i;
            --j;
        }
        if (i < 0) {
            //已经是最大字典序，结束
            return output;
        }
        //2、从j位置开始往numbers结尾查找，找到numbers[i]后面最后一个比numbers[i]大的数numbers[j]
        //解析：numbers[j]是i位置之后刚刚好比numbers[i]大的数，这样选numbers[j]的原因是下一个字典序是离现在的字典序最近的
        for (int k = j; k < n; ++k) {
            if (output[i] < output[k]) {
                j = k;
            }
        }
        //3、将i和j位置的字符对调
        //解析：此时numbers[j]被放到i位置，这样字典序就已经比input大很多了
        int t = output[j];
        output[j] = output[i];
        output[i] = t;
        //4、最后将(i+1)位置到结尾范围的字符翻转，即可得到下一个字典序结果
        //解析：注意到numbers[i+1]、numbers[i+2]...numbers[n-1]的排列是单调递减的，此段范围内字典序最大，通过翻转之后可以变成最小字典序
        //以上四步完成后即可得到最接近input的下一个字典序，因为numbers[j]是刚刚好比numbers[i]大，且i位置后的序列变成最小字典序
        int l = i + 1, r = n - 1;
        while (l < r) {
            t = output[l];
            output[l] = output[r];
            output[r] = t;
            ++l;
            --r;
        }
        return output;
    }

    /**
     * 返回下一个排列，如果没有下一个排列，则返回值为null
     */
    public static List<Integer> nextPermutation(List<Integer> input) {
        int n = input.size();
        //这里对input做了拷贝，操作过程不影响input
        Integer[] output = input.toArray(new Integer[0]);
        if (n < 2) {
            //少于2个字符长度的没有下一个字典序可言
            return null;
        }
        //1、从字符串结尾开始向头部扫描，找到第一个出现降序的字符，满足numbers[i] < numbers[j]，标记j位置
        //解析：能找到这样的位置，说明还存在存在更大的字典序
        int j = n - 1, i = j - 1;
        while (i >= 0) {
            if (output[i] < output[j]) {
                break;
            }
            --i;
            --j;
        }
        if (i < 0) {
            //已经是最大字典序，结束
            return null;
        }
        //2、从j位置开始往numbers结尾查找，找到numbers[i]后面最后一个比numbers[i]大的数numbers[j]
        //解析：numbers[j]是i位置之后刚刚好比numbers[i]大的数，这样选numbers[j]的原因是下一个字典序是离现在的字典序最近的
        for (int k = j; k < n; ++k) {
            if (output[i] < output[k]) {
                j = k;
            }
        }
        //3、将i和j位置的字符对调
        //解析：此时numbers[j]被放到i位置，这样字典序就已经比input大很多了
        int t = output[j];
        output[j] = output[i];
        output[i] = t;
        //4、最后将[i+1, n-1]范围的字符翻转，即可得到下一个字典序结果
        //解析：注意到numbers[i+1]、numbers[i+2]...numbers[n-1]的排列是单调递减的，此段范围内字典序最大，通过翻转之后可以变成最小字典序
        //以上四步完成后即可得到最接近input的下一个字典序，因为numbers[j]是刚刚好比numbers[i]大，且i位置后的序列变成最小字典序
        int l = i + 1, r = n - 1;
        while (l < r) {
            t = output[l];
            output[l] = output[r];
            output[r] = t;
            ++l;
            --r;
        }
        List<Integer> result = new ArrayList<>(n);
        result.addAll(Arrays.asList(output));
        return result;
    }

    /**
     * 返回是否有下一个排列，如果没有下一个排列，则返回值为false，如果有下一个排列，返回值为true，并且参数是下一个排列
     */
    public static boolean nextPermutationInPlace(Integer[] input) {
        int n = input.length;
        if (n < 2) {
            //少于2个字符长度的没有下一个字典序可言
            return false;
        }
        //1、从字符串结尾开始向头部扫描，找到第一个出现降序的字符，满足numbers[i] < numbers[j]，标记j位置
        //解析：能找到这样的位置，说明还存在存在更大的字典序
        int j = n - 1, i = j - 1;
        while (i >= 0) {
            if (input[i] < input[j]) {
                break;
            }
            --i;
            --j;
        }
        if (i < 0) {
            //已经是最大字典序，结束
            return false;
        }
        //2、从j位置开始往numbers结尾查找，找到numbers[i]后面最后一个比numbers[i]大的数numbers[j]
        //解析：numbers[j]是i位置之后刚刚好比numbers[i]大的数，这样选numbers[j]的原因是下一个字典序是离现在的字典序最近的
        for (int k = j; k < n; ++k) {
            if (input[i] < input[k]) {
                j = k;
            }
        }
        //3、将i和j位置的字符对调
        //解析：此时numbers[j]被放到i位置，这样字典序就已经比input大很多了
        int t = input[j];
        input[j] = input[i];
        input[i] = t;
        //4、最后将(i+1)位置到结尾范围的字符翻转，即可得到下一个字典序结果
        //解析：注意到numbers[i+1]、numbers[i+2]...numbers[n-1]的排列是单调递减的，此段范围内字典序最大，通过翻转之后可以变成最小字典序
        //以上四步完成后即可得到最接近input的下一个字典序，因为numbers[j]是刚刚好比numbers[i]大，且i位置后的序列变成最小字典序
        int l = i + 1, r = n - 1;
        while (l < r) {
            t = input[l];
            input[l] = input[r];
            input[r] = t;
            ++l;
            --r;
        }
        return true;
    }
}
